排列组合的一些公式及推导(非常详细易懂)

分类计数原理：做一件事，有\(n\)类办法，在第\(1\)类办法中有\(m_1\)种不同的方法，在第\(2\)类办法中有\(m_2\)种不同的方法，…，在第\(n\)类办法中有\(m_n\)种不同的方法，那么完成这件事共有\(N=m_1+m_2+…+m_n\)种不同的方法。

分步计数原理：完成一件事，需要分成\(n\)个步骤，做第\(1\)步有\(m_1\)种不同的方法，做第\(2\)步有\(m_2\)种不同的方法，…，做第\(n\)步有\(m_n\)种不同的方法,那么完成这件事共有\(N=m_1×m_2×\cdots ×m_n\)种不同的方法。

区别：分类计数原理是加法原理，不同的类加起来就是我要得到的总数；分步计数原理是乘法原理，是同一事件分成若干步骤，每个步骤的方法数相乘才是总数。

从\(n\)个不同元素种取出\(m(m\leq n)\)个元素的所有不同排列的个数，叫做从\(n\)个不同元素种取出\(m\)个元素的排列数，用符号\(A_n^m\)表示。

\[A_n^m=n(n-1)(n-2)\cdots(n-m+1)=\frac{n!}{(n-m)!},\quad n,m\in \mathbb{N}^* ,\text{并且}m\leq n \] （规定\(0!=1\)）

推导：把\(n\)个不同的元素任选\(m\)个排序，按计数原理分步进行：

取第一个：有\(n\)种取法； 取第二个：有\((n-1)\)种取法； 取第三个：有\((n-2)\)种取法； …… 取第\(m\)个：有\((n-m+1)\)种取法；

根据分步乘法原理，得出上述公式。

\(A_n^m = nA_{n-1}^{m-1}\) 可理解为“某特定位置”先安排，再安排其余位置。

\(A_n^m = mA_{n-1}^{m-1} + A_{n-1}^m\) 可理解为：含特定元素的排列有\(mA_{n-1}^{m-1}\)，不含特定元素的排列为\(A_{n-1}^m\)。

从\(n\)个不同元素种取出\(m(m\leq n)\)个元素的所有不同组合的个数，叫做从\(n\)个不同元素种取出\(m\)个元素的组合数，用符号\(C_n^m\)表示。

\[C_n^m=\frac{A_n^m}{A_m^m}=\frac{n(n-1)(n-2)\cdots (n-m+1)}{m!}=\frac{n!}{m